package data_structure;

public class leetcode_0086 {
    public ListNode partition(ListNode head, int x) {
        if(head==null) return null;
        ListNode p=head;
        ListNode root=new ListNode();
        ListNode q=root;
        while(p!=null){
            if(p.val<x) {
                q.val=p.val;

                q.next=new ListNode();
                q=q.next;
            }
            p=p.next;
        }
        p=head;
        while(p!=null){
            if(p.val>=x){
                q.val=p.val;
                q.next=new ListNode();
                q=q.next;
            }
            p=p.next;
        }
        q=root;
        p=root.next;
        while(p.next!=null){
            p=p.next;
            q=q.next;
        }
        q.next=null;
        return root;
    }
}
